/**
题目:
5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"
*/
/*

*/class Solution {
public:
    string longestPalindrome(string s) {
        //这是个dp问题
        //dp[i][j],表示字符串i到j的回文长度
        /*
        状态转移方程
        dp[i][j]=dp[i+1][j-1]+a[i]==a[j]
        */
        int size=s.size();
         int maxLen=0;
         int start=0;
       
        vector<vector<int>> dp(size,vector<int>(size,0));
        for(int i=size-1;i>=0;i--){
           
            for(int j=i;j<size;j++){
                 
                dp[i][j]=s[i]==s[j]&&(j-i<2||dp[i+1][j-1]);
                
               if(dp[i][j]>0&&j-i+1>maxLen){
                    maxLen=j-i+1;
                    start=i;
                }
            }
        }
        return  s.substr(start,maxLen);;
    }
};